#include <string.h>
#include <iostream>
#include "findSubString.h"

using namespace std;

bool findSubString(char *str, 
				   char *word, 
				   unsigned int &start, 
				   unsigned int &end) {
	if (str == NULL) {
		cout << "Input string is NULL!" << endl;
		start = end = 0;
		return false;
	}

	if (word == NULL) {
		cout << "Input word is NULL!" << endl;
		start = end = 0;
		return true;
	}

	size_t str_len = strlen(str);
	size_t word_len = strlen(word);

	// Meaning of the count
	// 0: no such a character in the word
	// 1: characters is in word, 
	// 2: one or more characters in the string match that in the word
	unsigned int count[256];
	memset(count, 0, sizeof(unsigned int) * 256);


	size_t i, j, win_size;
	win_size = str_len + 1;
	for (i = 0; i < word_len; i++) {
		count[word[i]] = 1;
	}
	
	unsigned int char_num = 0;
	bool check_start_flag = false;
	for (i = 0; i < 256; i++) {
		if (count[i] == 1) {
			++char_num;
		}
	}

	unsigned int loc = 0;
	start = end = 0;
	for (i = 0; i < str_len; i++) {
		if (count[str[i]] == 1) {
			count[str[i]]++;
			char_num--;
			if (char_num == 0) {
				check_start_flag = true;
			}
		}
		else if (count[str[i]] > 1) {
			count[str[i]]++;
			check_start_flag = true;
		}
		
		// all chars are found
		if (check_start_flag){
			while (loc < i + 1) {
				// has other such character
				if (count[str[loc]] == 0) {
					++loc;
				}
				else if (count[str[loc]] > 2) {
					++loc;
					--count[str[loc]];
				}
				else if (count[str[loc]] == 2) {
					break;
				}
			}
			
			if (win_size > i + 1- loc) {
				win_size = i + 1- loc;
				start = loc;
				end = i + 1;
			}
			check_start_flag = false;
		}
	}

	if (end == 0) {
		return false;
	}

	return true;
}

